package pers.qianyu.month_202012.date_20201212;

import org.junit.*;

import java.util.*;

/**
 * 496. 下一个更大元素 I
 * https://leetcode-cn.com/problems/next-greater-element-i/
 *
 * @author mizzle rain
 * @date 2020-12-12 16:34
 */
public class NextGreaterElement {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> dict = new HashMap<>();
        Stack<Integer> s = new Stack<>();
        for (int i = nums2.length - 1; i >= 0; i--) {
            int value = nums2[i];
            while (!s.isEmpty() && s.peek() <= value) {
                s.pop();
            }
            dict.put(value, s.isEmpty() ? -1 : s.peek());
            s.push(value);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = dict.get(nums1[i]);
        }
        return res;
    }

    @Test
    public void test1() {
        int[] nums1 = {4, 1, 2}, nums2 = {1, 3, 4, 2};
        int[] result = new NextGreaterElement().nextGreaterElement(nums1, nums2);
        System.out.println("result = " + Arrays.toString(result));
    }
}
